package JZ.JZ42;

/**
 * @author corn
 * @create 2020-08-13-19:19
 */


import java.util.ArrayList;
import java.util.HashMap;

/**
 * JZ42 和为S的两个数字
 * 题目描述
 * 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
 */
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
        ArrayList<Integer> integers = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0 ;i < array.length ;i++){
            int complement = sum - array[i];
            if (map.containsKey(complement)) {
                if( integers.isEmpty() ){//存储首个满足（和正好是S）要求的两个数
                    integers.add(array[map.get(complement)]);
                    integers.add(array[i]);
                }else if( integers.get(0)*integers.get(1) > array[i] * complement){//更换为乘积更小的两个数
                    integers.set(0,array[map.get(complement)]);
                    integers.set(1,array[i]);
                }
            }
            map.put(array[i], i);
        }
        return integers;
    }
}
